// Copyright 2015 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "src/identity-map.h"

#include "src/base/functional.h"
#include "src/heap/heap.h"
#include "src/roots-inl.h"

#include "src/objects-inl.h" // weolar

namespace v8 {
namespace internal {

    static const int kInitialIdentityMapSize = 4;
    static const int kResizeFactor = 2;

    IdentityMapBase::~IdentityMapBase()
    {
        // Clear must be called by the subclass to avoid calling the virtual
        // DeleteArray function from the destructor.
        DCHECK_NULL(keys_);
    }

    void IdentityMapBase::Clear()
    {
        if (keys_) {
            DCHECK(!is_iterable());
            heap_->UnregisterStrongRoots(FullObjectSlot(keys_));
            DeleteArray(keys_);
            DeleteArray(values_);
            keys_ = nullptr;
            values_ = nullptr;
            size_ = 0;
            capacity_ = 0;
            mask_ = 0;
        }
    }

    void IdentityMapBase::EnableIteration()
    {
        CHECK(!is_iterable());
        is_iterable_ = true;
    }

    void IdentityMapBase::DisableIteration()
    {
        CHECK(is_iterable());
        is_iterable_ = false;
    }

    int IdentityMapBase::ScanKeysFor(Address address) const
    {
        int start = Hash(address) & mask_;
        Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
        for (int index = start; index < capacity_; index++) {
            if (keys_[index] == address)
                return index; // Found.
            if (keys_[index] == not_mapped)
                return -1; // Not found.
        }
        for (int index = 0; index < start; index++) {
            if (keys_[index] == address)
                return index; // Found.
            if (keys_[index] == not_mapped)
                return -1; // Not found.
        }
        return -1;
    }

    int IdentityMapBase::InsertKey(Address address)
    {
        Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
        while (true) {
            int start = Hash(address) & mask_;
            int limit = capacity_ / 2;
            // Search up to {limit} entries.
            for (int index = start; --limit > 0; index = (index + 1) & mask_) {
                if (keys_[index] == address)
                    return index; // Found.
                if (keys_[index] == not_mapped) { // Free entry.
                    size_++;
                    DCHECK_LE(size_, capacity_);
                    keys_[index] = address;
                    return index;
                }
            }
            // Should only have to resize once, since we grow 4x.
            Resize(capacity_ * kResizeFactor);
        }
        UNREACHABLE();
    }

    bool IdentityMapBase::DeleteIndex(int index, void** deleted_value)
    {
        if (deleted_value != nullptr)
            *deleted_value = values_[index];
        Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
        DCHECK_NE(keys_[index], not_mapped);
        keys_[index] = not_mapped;
        values_[index] = nullptr;
        size_--;
        DCHECK_GE(size_, 0);

        if (capacity_ > kInitialIdentityMapSize && size_ * kResizeFactor < capacity_ / kResizeFactor) {
            Resize(capacity_ / kResizeFactor);
            return true; // No need to fix collisions as resize reinserts keys.
        }

        // Move any collisions to their new correct location.
        int next_index = index;
        for (;;) {
            next_index = (next_index + 1) & mask_;
            Address key = keys_[next_index];
            if (key == not_mapped)
                break;

            int expected_index = Hash(key) & mask_;
            if (index < next_index) {
                if (index < expected_index && expected_index <= next_index)
                    continue;
            } else {
                DCHECK_GT(index, next_index);
                if (index < expected_index || expected_index <= next_index)
                    continue;
            }

            DCHECK_EQ(not_mapped, keys_[index]);
            DCHECK_NULL(values_[index]);
            std::swap(keys_[index], keys_[next_index]);
            std::swap(values_[index], values_[next_index]);
            index = next_index;
        }

        return true;
    }

    int IdentityMapBase::Lookup(Address key) const
    {
        int index = ScanKeysFor(key);
        if (index < 0 && gc_counter_ != heap_->gc_count()) {
            // Miss; rehash if there was a GC, then lookup again.
            const_cast<IdentityMapBase*>(this)->Rehash();
            index = ScanKeysFor(key);
        }
        return index;
    }

    int IdentityMapBase::LookupOrInsert(Address key)
    {
        // Perform an optimistic lookup.
        int index = ScanKeysFor(key);
        if (index < 0) {
            // Miss; rehash if there was a GC, then insert.
            if (gc_counter_ != heap_->gc_count())
                Rehash();
            index = InsertKey(key);
        }
        DCHECK_GE(index, 0);
        return index;
    }

    int IdentityMapBase::Hash(Address address) const
    {
        CHECK_NE(address, ReadOnlyRoots(heap_).not_mapped_symbol().ptr());
        return static_cast<int>(hasher_(address));
    }

    // Searches this map for the given key using the object's address
    // as the identity, returning:
    //    found => a pointer to the storage location for the value
    //    not found => a pointer to a new storage location for the value
    IdentityMapBase::RawEntry IdentityMapBase::GetEntry(Address key)
    {
        CHECK(!is_iterable()); // Don't allow insertion while iterable.
        if (capacity_ == 0) {
            // Allocate the initial storage for keys and values.
            capacity_ = kInitialIdentityMapSize;
            mask_ = kInitialIdentityMapSize - 1;
            gc_counter_ = heap_->gc_count();

            keys_ = reinterpret_cast<Address*>(NewPointerArray(capacity_));
            Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
            for (int i = 0; i < capacity_; i++)
                keys_[i] = not_mapped;
            values_ = NewPointerArray(capacity_);
            memset(values_, 0, sizeof(void*) * capacity_);

            heap_->RegisterStrongRoots(FullObjectSlot(keys_),
                FullObjectSlot(keys_ + capacity_));
        }
        int index = LookupOrInsert(key);
        return &values_[index];
    }

    // Searches this map for the given key using the object's address
    // as the identity, returning:
    //    found => a pointer to the storage location for the value
    //    not found => {nullptr}
    IdentityMapBase::RawEntry IdentityMapBase::FindEntry(Address key) const
    {
        // Don't allow find by key while iterable (might rehash).
        CHECK(!is_iterable());
        if (size_ == 0)
            return nullptr;
        // Remove constness since lookup might have to rehash.
        int index = Lookup(key);
        return index >= 0 ? &values_[index] : nullptr;
    }

    // Deletes the given key from the map using the object's address as the
    // identity, returning true iff the key was found (in which case, the value
    // argument will be set to the deleted entry's value).
    bool IdentityMapBase::DeleteEntry(Address key, void** deleted_value)
    {
        CHECK(!is_iterable()); // Don't allow deletion by key while iterable.
        if (size_ == 0)
            return false;
        int index = Lookup(key);
        if (index < 0)
            return false; // No entry found.
        return DeleteIndex(index, deleted_value);
    }

    Address IdentityMapBase::KeyAtIndex(int index) const
    {
        DCHECK_LE(0, index);
        DCHECK_LT(index, capacity_);
        DCHECK_NE(keys_[index], ReadOnlyRoots(heap_).not_mapped_symbol().ptr());
        CHECK(is_iterable()); // Must be iterable to access by index;
        return keys_[index];
    }

    IdentityMapBase::RawEntry IdentityMapBase::EntryAtIndex(int index) const
    {
        DCHECK_LE(0, index);
        DCHECK_LT(index, capacity_);
        DCHECK_NE(keys_[index], ReadOnlyRoots(heap_).not_mapped_symbol().ptr());
        CHECK(is_iterable()); // Must be iterable to access by index;
        return &values_[index];
    }

    int IdentityMapBase::NextIndex(int index) const
    {
        DCHECK_LE(-1, index);
        DCHECK_LE(index, capacity_);
        CHECK(is_iterable()); // Must be iterable to access by index;
        Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
        for (++index; index < capacity_; ++index) {
            if (keys_[index] != not_mapped) {
                return index;
            }
        }
        return capacity_;
    }

    void IdentityMapBase::Rehash()
    {
        CHECK(!is_iterable()); // Can't rehash while iterating.
        // Record the current GC counter.
        gc_counter_ = heap_->gc_count();
        // Assume that most objects won't be moved.
        std::vector<std::pair<Address, void*>> reinsert;
        // Search the table looking for keys that wouldn't be found with their
        // current hashcode and evacuate them.
        int last_empty = -1;
        Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
        for (int i = 0; i < capacity_; i++) {
            if (keys_[i] == not_mapped) {
                last_empty = i;
            } else {
                int pos = Hash(keys_[i]) & mask_;
                if (pos <= last_empty || pos > i) {
                    // Evacuate an entry that is in the wrong place.
                    reinsert.push_back(std::pair<Address, void*>(keys_[i], values_[i]));
                    keys_[i] = not_mapped;
                    values_[i] = nullptr;
                    last_empty = i;
                    size_--;
                }
            }
        }
        // Reinsert all the key/value pairs that were in the wrong place.
        for (auto pair : reinsert) {
            int index = InsertKey(pair.first);
            DCHECK_GE(index, 0);
            values_[index] = pair.second;
        }
    }

    void IdentityMapBase::Resize(int new_capacity)
    {
        CHECK(!is_iterable()); // Can't resize while iterating.
        // Resize the internal storage and reinsert all the key/value pairs.
        DCHECK_GT(new_capacity, size_);
        int old_capacity = capacity_;
        Address* old_keys = keys_;
        void** old_values = values_;

        capacity_ = new_capacity;
        mask_ = capacity_ - 1;
        gc_counter_ = heap_->gc_count();
        size_ = 0;

        keys_ = reinterpret_cast<Address*>(NewPointerArray(capacity_));
        Address not_mapped = ReadOnlyRoots(heap_).not_mapped_symbol().ptr();
        for (int i = 0; i < capacity_; i++)
            keys_[i] = not_mapped;
        values_ = NewPointerArray(capacity_);
        memset(values_, 0, sizeof(void*) * capacity_);

        for (int i = 0; i < old_capacity; i++) {
            if (old_keys[i] == not_mapped)
                continue;
            int index = InsertKey(old_keys[i]);
            DCHECK_GE(index, 0);
            values_[index] = old_values[i];
        }

        // Unregister old keys and register new keys.
        heap_->UnregisterStrongRoots(FullObjectSlot(old_keys));
        heap_->RegisterStrongRoots(FullObjectSlot(keys_),
            FullObjectSlot(keys_ + capacity_));

        // Delete old storage;
        DeleteArray(old_keys);
        DeleteArray(old_values);
    }

} // namespace internal
} // namespace v8
